#include <bits/stdc++.h>

using namespace std;

int n,cnt;
bool hassetl[20],hasseta[30],hassetb[30];
int a[20];
void pr(){
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
    cout<<endl;
}
void dfs(int x){
    if(x>=n+1){
        cnt++;
        if(cnt<=3){
            pr();
        }
        return;
    }
    for(int i=1;i<=n;i++){
        if(!hassetl[i]&&!hasseta[x-i+n]&&!hassetb[x+i]){
            a[x] = i;
            hassetl[i] = 1;
            hasseta[x-i+n] = 1;
            hassetb[x+i] = 1;
            dfs(x+1);
            hassetl[i] = 0;
            hasseta[x-i+n] = 0;
            hassetb[x+i] = 0;
        }
    }
    return;
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<cnt;
    return 0;
}
